package cn.algorithms_4ed.algo.sort;

/**
 * Merge
 * <p/>
 * 统计显示，如果数组长度为N，
 * 平均比较次数为
 * 平均交换次数约为
 * <p/>
 * User: erhu
 * Date: 13-6-15
 * Time: 上午11:17
 */
public class Merge extends Sort {

    private Comparable[] aux;

    public static void main(String[] args) {
        Merge merge = new Merge();
        merge.sort().show();
    }

    @Override
    Sort sort() {
        aux = new Comparable[data.length];
        sort(0, data.length - 1);
        return this;
    }

    private void sort(int low, int high) {
        if (high <= low) {
            return;
        }
        int mid = low + (high - low) / 2;

        sort(low, mid);
        sort(mid + 1, high);
        merge(low, mid, high);
    }

    private void merge(int low, int mid, int high) {
        int i = low, j = mid + 1;

        System.arraycopy(data, low, aux, low, high - low + 1);

        for (int k = low; k <= high; k++) {
            // 右边的数小
            if (i <= mid && j <= high && less(aux[j], aux[i])) {
                data[k] = aux[j++];
            }
            // 右边的数小
            else if (i <= mid && j <= high && less(aux[i], aux[j])) {
                data[k] = aux[i++];
            }
            // 左边用完
            else if (i > mid) {
                data[k] = aux[j++];
            }
            // 右边用完
            else if (j > high) {
                data[k] = aux[i++];
            }
        }
    }
}
